Tiling a rectangle with the fewest squares

Time: O(N2xM2xM^(NxM)); Space: O(NxM); hard

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3

Output: 3

Explanation:

  • 3 squares are necessary to cover the rectangle.

  • 2 (squares of 1x1)

  • 1 (square of 2x2)

Example 2:

Input: n = 5, m = 8

Output: 5

Example 3:

Input: n = 11, m = 13

Output: 6

Constraints:

  • 1 <= n <= 13

  • 1 <= m <= 13

Hints:

  1. Can you use backtracking to solve this problem ?.

  2. Suppose you’ve placed a bunch of squares. Where is the natural spot to place the next square ?.

  3. The maximum number of squares to be placed will be ≤ max(n,m).

[1]:

class Solution1(object):
    """
    Time: O(N^2*M^2*M^(N*M)), given M < N
    Space: O(N*M)
    """
    def tilingRectangle(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        def find_next(board):
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if not board[i][j]:
                        return i, j
            return -1, -1

        def find_max_length(board, i, j):
            max_length = 1
            while i+max_length-1 < len(board) and \
                  j+max_length-1 < len(board[0]):

                for r in range(i, i+max_length-1):
                    if board[r][j+max_length-1]:
                        return max_length-1

                for c in range(j, j+max_length):
                    if board[i+max_length-1][c]:
                        return max_length-1
                max_length += 1
            return max_length-1

        def fill(board, i, j, length, val):
            for r in range(i, i+length):
                for c in range(j, j+length):
                    board[r][c] = val

        def backtracking(board, count, result):
            if count >= result[0]:  # pruning
                return
            i, j = find_next(board)
            if (i, j) == (-1, -1):  # finished
                result[0] = min(result[0], count)
                return

            max_length = find_max_length(board, i, j)
            for k in reversed(range(1, max_length+1)):
                fill(board, i, j, k, 1)
                backtracking(board, count+1, result)
                fill(board, i, j, k, 0)

        if m > n:
            return self.tilingRectangle(m, n)
        board = [[0]*m for _ in range(n)]
        result = [float("inf")]
        backtracking(board, 0, result)

        return result[0]

[2]:

s = Solution1()
n = 2
m = 3
assert s.tilingRectangle(n, m) == 3
n = 5
m = 8
assert s.tilingRectangle(n, m) == 5
n = 11
m = 13
assert s.tilingRectangle(n, m) == 6